﻿#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>
int main()
{
//数组
 //⼀维数组创建的基本语法如下：
	//type arr_name[常量值];
	// type 指定的是数组中存放数据的类型，可以是： char、short、int、float 等，也可以自定义的类型。
	// arr_name 指的是数组名的名字，这个名字根据实际情况，起的有意义就⾏。
	// [] 中的常量值是用来指定数组的大小的，这个数组的大小是根据实际的需求指定就⾏。
	
	//int arr1[10] = {1, 2, 3, 4}; //不完全初始化,剩余的值默认初始化为0
	//int arr2[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; //完全初始化

	//数组如果初始化了，那么可以不指定数组的大小，数组的大小是根据初始化的内容来推算
	//int arr3[] = { 1,2,3 };
	//char arr1[6] = "abc"; //a b c \0 0 0，数字0表示为'\0'
	//char arr2[6] = { 'a', 'b', 'c' }; //a b c 0 0 0

//数组的类型
	//数组也是有类型的，数组算是⼀种⾃定义类型，“去掉数组名”留下的就是数组的类型。如下：
	//int arr1[10];
	//int arr2[12];
	//char ch[5];
	// arr1 数组的类型是 int[10]  
	// arr2 数组的类型是 int[12]  
	// ch 数组的类型是 char[5] 
	//	printf("%zd\n", sizeof(arr1)); //40
    //	printf("%zd\n", sizeof(int [10])); //40

//数组下标
	//下标是从0开始的，假设数组有n个元素，最后⼀个元素的下标是 n-1 ，下标就相当于数组元素的编号
	//在C语言中数组的访问提供了⼀个操作符 [] ，这个操作符叫：下标引用操作符。
	//int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	                //0 1 2 3 4 5 6 7 8 9
	//printf("%d\n", arr[4]); //[] 下标引用操作符
	//printf("%d\n", arr[7]); //[] 下标引用操作符

//数组元素的打印
    //只要我们产生数组所有元素的下标就可以了，那我们使⽤for循环产⽣0~9的下标，接下来使用下标访问就⾏了。
	//int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//int i = 0;
	//for (i = 0; i < 10; i++)
	//{
	//	printf("%d ", arr[i]);
	//}

//数组的输入
	//明白了数组的访问，当然我们也根据需求，⾃⼰输入想要的数据
	//int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//int i = 0;
	///for (i = 0; i < 10; i++)
	//{
	//	scanf("%d", &arr[i]); //10 9 8 7 6 5 4 3 2 1
	//}
	//for (i = 0; i < 10; i++)
	//{
	//	printf("%d ", arr[i]); //10 9 8 7 6 5 4 3 2 1
	//}

//⼀维数组在内存中的存储
	//依次打印数组元素的地址：
	//int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//int i = 0;
	//for (i = 0; i < 10; i++)
	//{
	//	printf("&arr[%d] = %p\n", i, &arr[i]);
	//}
	//其中一次的输出结果为：
	//& arr[0] = 003EFE04
	//& arr[1] = 003EFE08
	//& arr[2] = 003EFE0C
	//& arr[3] = 003EFE10
	//& arr[4] = 003EFE14
	//& arr[5] = 003EFE18
	//& arr[6] = 003EFE1C
	//& arr[7] = 003EFE20
	//& arr[8] = 003EFE24
	//& arr[9] = 003EFE28
	//从输出的结果我们分析，数组随着下标的增⻓，地址是由小到大变化的，
	//并且我们发现每两个相邻的元素之间相差4（因为⼀个整型是4个字节）。
	//所以我们得出结论：数组在内存中是“连续存放”的。

// sizeof 计算数组元素个数
	// sizeof 是C语言中⼀个关键字，是可以计算类型或者变量大小的，其实 sizeof 也可以计算数组的⼤⼩。
	//int arr[20] = { 0 };
	//int sz = sizeof(arr) / sizeof(arr[0]);
	////       数组的总长度/一个元素的长度
	//printf("%d\n", sz); //20

//⼆维数组
//⼆维数组的概念
	//前面学习的数组被称为⼀维数组，数组的元素都是内置类型的，
	//如果我们把“⼀维数组”做为“数组的元素”，这时候就是⼆维数组，
	//⼆维数组作为数组元素的数组被称为三维数组，⼆维数组以上的数组统称为多维数组。

//⼆维数组的创建
	//语法如下：
	// type arr_name[常量值1][常量值2]；
	//例如：
	// int arr[3][5];
	// double data[2][8];
	//上述代码中出现的信息
	//常量值1表示数组的行
	//常量值2表示每一行的元素个数(即列)
	// type 表示数组元素的类型
	// arr 是数组名，可以根据自己的需要指定名字

//⼆维数组的初始化
    //像⼀维数组⼀样，也是使用⼤括号初始化的。
    //不完全初始化
    //int arr1[3][5] = { 1,2 };
    //int arr2[3][5] = { 0 };
	
    //完全初始化
    //int arr3[3][5] = { 1,2,3,4,5, 2,3,4,5,6, 3,4,5,6,7 };

    //按照行初始化
    //int arr4[3][5] = { {1,2},{3,4},{5,6} };
	//打印结果为：1 2 0 0 0
    //            3 4 0 0 0
    //            5 6 0 0 0

    //初始化时省略行，但是不能省略列
	// int arr5[][5] = { 1,2,3 }; 
	// int arr6[][5] = { 1,2,3,4,5,6,7 };
	// int arr7[][5] = { {1,2}, {3,4}, {5,6} };
    //若已知每行最多存放的元素个数，可通过计算算出有多少行，数组是确定的，即可以省略行
    //但只已知行数而不知道每行最多存放的元素个数，会导致可能会出现多种存放方式，数组不确定，故不能省列

//⼆维数组的使用
    //⼆维数组的下标
    //int arr[3][5] = { 1,2,3,4,5, 2,3,4,5,6, 3,4,5,6,7 };
    //printf("%d\n", arr[2][4]); //[]下标引用操作符
    //C语言规定，二维数组的行是从0开始的，列也是从0开始的
    //即arr[2][4]的元素值为7

//⼆维数组的输入和输出
    //输入并打印数组的所有元素
    //int arr[3][5] = { 0 };
	////输入数据
	//int i = 0;
	//for (i = 0; i < 3; i++) //产生行号
	//{
	//	int j = 0;
	//	for (j = 0; j < 5; j++) //产生列号
	//	{
	//		scanf("%d", &arr[i][j]); //输入数据
	//	}
	//}
	////打印数组中的所有元素-输出
	//for (i = 0; i < 3; i++)
	//{
	//	int j = 0;
	//	for (j = 0; j < 5; j++)
	//	{
	//		printf("%d ", arr[i][j]);
	//	}
	//	printf("\n");
	//}

//⼆维数组在内存中的存储
    //int i = 0;
	//int arr[2][4] = { 0 };
	//for (i = 0; i < 2; i++)
	//{
	//	int j = 0;
	//	for (j = 0; j < 4; j++)
	//	{
	//		printf("&arr[%d][%d] = %d\n",i, j, &arr[i][j]);
	//	}
	//}
	//其中一次的输出结果为：
	//& arr[0][0] = 9435080
	//& arr[0][1] = 9435084
	//& arr[0][2] = 9435088
	//& arr[0][3] = 9435092
	//& arr[1][0] = 9435096
	//& arr[1][1] = 9435100
	//& arr[1][2] = 9435104
	//& arr[1][3] = 9435108
	//从输出的结果来看，每⼀行内部的每个元素都是相邻的，地址之间相差4个字节，
	//跨行位置处的两个元素（如：arr[0][3]和arr[1][0]）之间也是差4个字节，
	//所以二维数组中的每个元素都是“连续存放”的，第二行数组是紧跟在第一行之后的。
	//了解清楚二维数组在内存中的布局，有利于我们后期使用指针来访问数组的学习。

//数组练习
    //多个字符从两端移动，向中间汇聚
    //char arr1[] = "welcome to the world!";
    //char arr2[] = "#####################";
	//int left = 0;
	//int right = strlen(arr1) - 1; //sizeof(arr2) / sizeof(arr2[0]) - 2 这个写法也可以
	//printf("%s\n", arr2);
	//while (left <= right)
	//{
	//	arr2[left] = arr1[left];
	//	arr2[right] = arr1[right];
	//	Sleep(1000); //睡眠函数，单位是毫秒，作用是延时打印内容。Sleep的S要大写
	//	system("cls"); //“cls”之前已经提到过了是系统命令的删除内容作用
	//	left++;
	//	right--;
	//	printf("%s\n", arr2);
	//}

//在⼀个升序的数组中查找指定的数字n
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int n = 0;
	scanf("%d", &n); //我们要在数组arr中找到n中的数字
//1.遍历数组（挨个找）（不够高效）
	//int sz = sizeof(arr) / sizeof(arr[0]); //计算数组的元素个数
	//int i = 0;
	//for (i = 0; i < sz; i++)
	//{
	//	if (n == arr[i])
	//	{
	//		printf("找到了，下标是%d\n", i);
	//		break;
	//	}
	//	if (i == (sz - 1))
	//	{
	//		printf("找不到");
	//	}
	//}

//2.二分查找（折半查找）（数组必须是升序或降序，不能乱序）
	int left = 0;
	int right = sizeof(arr) / sizeof(arr[0]) - 1;
	int flag = 0; // 假定找不到
	while (left <= right)
	{
		//int mid = (left + right) / 2; //此方法求中间值可能有问题，如果left和right⽐较⼤的时候可能超过int最大值
		int mid = left + (right - left) / 2;
		//这种方法避免了超过int类型最大值可能性，并且不会出现中间值求错的情况。
		//如果是mid = left / 2 + right / 2 这样的确也能避免超过最大值，但如果两者都是奇数时求出来的中间值会偏小，
		//原因是int类型奇数除2都会往下取整，两个都是奇数除2都会往下去整使得计算值比中间值小1
		//而mid = left + (right - left) / 2 避免了这个情况因为至多有一个为奇数就是right - left，故中间值偏小
		if (arr[mid] < n)
		{
		//	if (left == right)
		//	{
		//		printf("找不到\n"); //注释部分是另一种写法。此时可以不用加新变量 int flag 去假定
		//		break;
		//	}
			left = mid + 1;
		}
		else if (arr[mid] > n)
		{
		//	if (left == right)
		//	{
		//		printf("找不到\n");
		//		break;
		//	}
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标是%d\n", mid);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
	{
		printf("找不到\n");
	}

	return 0;
}